1870D - Prefix Purchase - CodeForces Solution

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include <bits/stdc++.h>
#ifdef LOCAL
#define DBG(X...) eprn(__func__,__LINE__,':',X)
#else
#define DBG(...)
#define endl '\n' // remove this line for interactive tasks
#ifdef assert
#undef assert
#endif
#define assert(expr) (expr) || (__builtin_unreachable(), 0)
#endif
#define FORT(T, I, S, N) for(T I = (S); I < (N); ++I)
#define RFORT(T, I, S, N) for(T I = (S); I > (N); --I)
#define FOR(I, S, N) FORT(ptrdiff_t, I, (S), (N)) // ptrdiff_t = basically same as isize in rust
#define RFOR(I, S, N) RFORT(ptrdiff_t, I, (S), (N))
#define FORI(N) FOR(i, 0, (N))
#define FORJ(N) FOR(j, 0, (N))
#define FORK(N) FOR(k, 0, (N))
#define SPOON(N) RFOR(k, (N)-1, -1)
#define ALL(X) (X).begin(), (X).end()
#define RALL(X) (X).rbegin(), (X).rend()
#define RD(T, ...) T __VA_ARGS__; rd(__VA_ARGS__);
#define YN(B) ((B)?"YES":"NO")
#define  A auto
#define _T template
#define _Y typename
#define _SP(A,B,C) bool f=!0;for(A){if(f){f=!1;}else{B;}C;}
#define _I1(C) _T<_Y T>ostream&operator<<(ostream&o,C<T>const&v){_SP(const A&x:v,o<<' ',o<<x)return o;}_T<_Y T>istream&operator>>(istream&i,C<T>&v){for(A&x:v){i>>x;}return i;}
#define _I2(C) _T<_Y T,_Y Y>ostream&operator<<(ostream&o,C<T,Y>const&v){_SP(const auto&x:v,o<<endl,o<<x)return o;}
using namespace std;constexpr long double PI=3.1415926535897932384626433832795029L;_T<_Y T>using V=vector<T>;_T<_Y T,_Y Y>using P=pair<T,Y>;_T<_Y K>using uset=unordered_set<K>;_T<_Y K>using umultiset=unordered_multiset<K>;_T<_Y K,_Y V>using umap=unordered_map<K,V>;_T<_Y K,_Y V>using umultimap=unordered_multimap<K,V>;using i64=int64_t;using u64=uint64_t;using ll=i64;using i32=int32_t;using u32=uint32_t;using I=i32;using i16=int16_t;using u16=uint16_t;using i8=int8_t;using u8=uint8_t;_I1(V);_I1(set);_I1(multiset);_I1(unordered_set);_I1(unordered_multiset);_I1(deque);_I1(queue);_I2(map);_I2(multimap);_I2(unordered_map);_I2(unordered_multimap);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());_T<_Y T,_Y Y>bool umin(T&a,const Y&b){return b<a&&(a=b,!0);}_T<_Y T,_Y Y>bool umax(T&a,const Y&b){return b>a&&(a=b,!0);}_T<_Y T,_Y Y>ostream&operator<<(ostream&o,pair<T,Y>const&p){return o<<p.first<<' '<<p.second;}_T<_Y T,_Y Y>istream&operator>>(istream&i,pair<T,Y>&p){return i>>p.first>>p.second;}_T<_Y T,size_t N>ostream&operator<<(ostream&o,array<T,N>const&v){_SP(const A&x:v,o<<' ',o<<x)return o;}_T<_Y T,size_t N>istream&operator>>(istream&i,array<T,N>&v){for(A&x:v){i>>x;}return i;}_T<size_t S=0,_Y...T>struct _Tio{static inline void i(istream&i,tuple<T...>&t){if constexpr(S<sizeof...(T)){i>>get<S>(t);_Tio<S+1,T...>::i(i,t);}}static inline void o(ostream&o,tuple<T...>const&t){if constexpr(S<sizeof...(T)){if(S)o<<' ';o<<get<S>(t);_Tio<S+1,T...>::o(o,t);}}};_T<_Y...T>istream&operator>>(istream&i,tuple<T...>&t){return _Tio<0,T...>::i(i,t),i;}_T<_Y...T>ostream&operator<<(ostream&o,tuple<T...>&t){return _Tio<0,T...>::o(o,t),o;}_T<_Y...S>inline void rd(S&...a){A t=forward_as_tuple(a...);cin>>t;}_T<_Y T>inline T read(){T x;cin>>x;return x;}_T<_Y T>inline V<T>read(size_t n){V<T>v(n);for(T&x:v)cin>>x;return v;}_T<_Y...S>inline void pr(const S&...a){(cout<<...<<a);}_T<_Y ...S>inline void prn(const S&...a){(cout<<...<<a)<<endl;}_T<_Y...S>inline void spr(const S&...a){A t=forward_as_tuple(a...);cout<<t;}_T<_Y...S>inline void sprn(const S&...a){spr(a...);cout<<endl;}_T<_Y...S>inline void epr(const S&...a){A t=forward_as_tuple(a...);cerr<<t<<' ';}_T<_Y...S>inline void eprn(const S&...a){epr(a...);cerr<<endl;}
 
void solve() {
  RD(ll, n); // a/c cnt
  A c = read<ll>(n); // c[i]: a[..=i] += 1
  RD(ll, k); // coins
  RFOR(i,n-1,0) {
    umin(c[i-1], c[i]);
    c[i] -= c[i-1];
  }
  ll ans = INT64_MAX;
  FORI(n) {
    if (c[i]) {
      umin(ans, k / c[i]);
      k -= c[i] * ans;
    }
    pr(ans, " \n"[i+1==n]);
  }
}
 
int main() {ios_base::sync_with_stdio(!1);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(15);srand(chrono::steady_clock::now().time_since_epoch().count());
  RD(I, t);
  FORI(t) solve();
}